package com.fmm.hard;

import java.util.*;

public class ZumaGame {

    /**
     * @param board: 球的排列状态，有5种颜色，分别用R, Y, B, G, W表示，最长长度为 16
     * @param hand:  手里球的颜色，有5种颜色，分别用R, Y, B, G, W表示，最长长度为 5
     * @return 返回使 board 清空所需要使用的最少球数，如果无法清空，返回 -1
     */
    public static int findMinStep(String board, String hand) {
        // 构建手里球的所有排列组合，并去重
        Set<String> handSet = generateHandSet(hand);
        int result = Integer.MAX_VALUE;
        // 尝试手里球的所有出球方法，找到最少的那一种
        for (String h : handSet) {
            char[] handCharArray = h.toCharArray();
            // 缓存加速
            // key : board + "_" + hand
            // value : 消除的最小球数
            Map<String, Integer> cache = new HashMap<>();
            // 广度优先队列
            Queue<Status> waiting = new LinkedList<>();
            waiting.offer(new Status(board, new String(handCharArray), 0));

            Status status;
            while ((status = waiting.poll()) != null) {
                String iHand = status.hand();
                String iBoard = status.board();
                Integer hasUsedCount = status.hasUsedCount();
                Integer cachedCount = cache.get(iBoard + "_" + sortHand(iHand));
                if (cachedCount != null) {
                    result = Math.min(result, cachedCount);
                    continue;
                }
                handCharArray = iHand.toCharArray();
                // 构建台面球链表，方便插入消除
                LinkedList<Character> boardList = generateBoard(iBoard);
                // 尝试把手里的每个球插入每个空隙
                for (int i = 0; i < handCharArray.length; i++) {
                    char c = handCharArray[i];
                    for (int p = 0; p <= iBoard.length(); p++) {
                        // 减枝：插入的位置的上一个他相同，不需要尝试，直接进入下一个位置
                        if (p > 0 && boardList.get(p - 1) == c) {
                            continue;
                        }
                        // 减枝：
                        // 插入的位置不是最后一个，同时他自己不是第一个，此时比较他前后两个，如果前后两个和他自己颜色互不相同，不用尝试
                        if (p < iBoard.length() && p > 0
                                && boardList.get(p - 1) != boardList.get(p)
                                && boardList.get(p - 1) != c
                                && boardList.get(p) != c) {
                            continue;
                        }
                        LinkedList<Character> boardListCopy = new LinkedList<>(boardList);
                        // 计算台面球在 p 位置 插入 c 球后的结果
                        calculateResult(boardListCopy, c, p);
                        // 如果已经消完了，返回次数 + 1，并缓存结果
                        if (boardListCopy.size() == 0) {
                            // 缓存当前结果
                            cache.put(iBoard + "_" + sortHand(iHand), hasUsedCount + 1);
                            return hasUsedCount + 1;
                        }
                        // 如果没消完，把状态放入广度优先队列
                        waiting.offer(new Status(
                                boardListCopy.stream().map(ch -> String.valueOf(ch)).reduce((a, b) -> a + b).get(),
                                iHand.substring(i + 1),
                                hasUsedCount + 1));
                    }
                }
            }
        }
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    // 对手球排序，用作缓存 key
    private static String sortHand(String hand) {
        char[] handArray = hand.toCharArray();
        Arrays.sort(handArray);
        return new String(handArray);
    }
    // 计算手球的所有排列组合（去重）
    private static Set<String> generateHandSet(String hand) {
        Set<String> result = new HashSet<>();
        // 使用广度优先队列
        Queue<StringBuilder> queue = new LinkedList<>();
        for (int i = 0; i < hand.length(); i++) {
            if (i == 0) {
                queue.offer(new StringBuilder(String.valueOf(hand.charAt(i))));
                continue;
            }
            // 同样长度的所有字符串拿出来遍历
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                StringBuilder s = queue.poll();
                // 对于拿出来的字符串，在字符串的所有间隙插入新字符，并放入广度队列
                for (int j = 0; j < s.length() + 1; j++) {
                    StringBuilder temp = new StringBuilder(s);
                    temp.insert(j, hand.charAt(i));
                    queue.offer(temp);
                }
            }
        }
        // 广度队列中已经是所有的排列组合，拿出来放入结果并去重
        StringBuilder sb;
        while ((sb = queue.poll()) != null) {
            result.add(sb.toString());
        }
        return result;
    }

    // 状态类，桌面球 + 手球，并记录到这个状态已使用了多少球
    private record Status(String board, String hand, Integer hasUsedCount) {
    }

    // 把桌面球转换成链表方便插入删除
    private static LinkedList<Character> generateBoard(String board) {
        LinkedList<Character> result = new LinkedList<>();
        for (char c : board.toCharArray()) {
            result.add(c);
        }
        return result;
    }

    // 计算在桌面球的 p 位置插入 ball
    private static void calculateResult(LinkedList<Character> board, char ball, int p) {
        board.add(p, ball);
        if (p + 1 > (board.size() - 1) || p + 2 > (board.size() - 1)) {
            return;
        }
        if (board.get(p) == board.get(p + 1) && board.get(p) == board.get(p + 2)) {
            for (int j = p + 2; j >= p; j--) {
                board.remove(j);
            }
            calculateResult(board, p);
        }
    }

    // 消除后的连锁消除逻辑
    private static void calculateResult(LinkedList<Character> board, int p) {
        int pre = p - 1;
        int post = p;
        if (pre < 0 || post >= board.size() || board.get(pre) != board.get(post)) {
            return;
        }
        Character preChar = board.get(pre);
        if (pre - 1 >= 0 && board.get(pre - 1) == preChar) {
            pre = pre - 1;
        }
        if (post + 1 < board.size() && board.get(post + 1) == preChar) {
            post = post + 1;
        }
        if (post - pre > 1) {
            for (int i = post; i >= pre; i--) {
                board.remove(i);
            }
            calculateResult(board, pre);
        }
    }

    public static void main(String[] args) {
        String board = "RRGGBBYYWWRRGGBB";
        String hand = "RGBYW";
        System.out.println("board: " + board + ", hand: " + hand + ", result: " + findMinStep(board, hand));
    }
}
